/**
 * @file big_integer.tcc
 * @purpose implements big_integer.hpp
 */

#ifndef __BIG_INTEGER_TCC__
#define __BIG_INTEGER_TCC__

#include <functional>
#include <algorithm>

BIG_NUMBERS_NAMESPACE_BEGIN

template <typename traits>
uinteger<traits>::uinteger()
{
        *this = zero;
}

template <typename traits>
uinteger<traits>::uinteger(unsigned int i)
{
        from_int(i);
}

template <typename traits>
uinteger<traits>::uinteger(digit d)
{
        push_back(d);
        check_invalid_digits();
}

template <typename traits>
uinteger<traits>::uinteger(const string& s)
{
        from_string(s);
}

template <typename traits>
uinteger<traits>::uinteger(const digits& d): base_type(d.rbegin(), d.rend())
{
        normalize();
        check_invalid_digits();
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator=(digit d)
{
        clear();
        push_back(d);
        check_invalid_digits();
        return *this;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator=(unsigned int i)
{
        from_int(i);
        return *this;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator=(const string& s)
{
        from_string(s);
        return *this;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator=(const digits& d)
{
        clear();
        insert(begin(), d.rbegin(), d.rend());
        normalize();
        check_invalid_digits();
        return *this;
}

template <typename traits>
bool uinteger<traits>::good_digit(digit d)
{
        return traits::is_digit(d);
}

template <typename traits>
bool uinteger<traits>::has_invalid_digits()
{
        return std::find_if(begin(), end(), std::not1(std::ptr_fun(good_digit))) != end();
}

template <typename traits>
void uinteger<traits>::check_invalid_digits()
{
        if (has_invalid_digits())
        {
                *this = zero;
                throw invalid_digit();
        }
}

template <typename traits>
void uinteger<traits>::check_invalid_base_10_digit(char_type c)
{
        if (c < '0' || c > '9')
        {
                throw invalid_digit();
        }
}

template <typename traits>
void uinteger<traits>::check_invalid_string(const string& s)
{
        std::for_each(s.begin(), s.end(), check_invalid_base_10_digit);
}

template <typename traits>
void uinteger<traits>::normalize()
{
        reverse_iterator it = std::find_if(rbegin(), rend(),
                                           std::not1(std::bind2nd(std::equal_to<digit>(), 0)));
        if (it != rbegin())
        {
                erase(it.base(), end());
        }
        if (empty())
        {
                *this = zero;
        }
        ASSERT(!has_invalid_digits());
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator ++()
{
        iterator cur = begin();
        while (cur != end() && *cur == max_digit) { *cur++ = 0; }
        if (cur != end())
        {
                ++(*cur);
        }
        else
        {
                // all digits were max
                push_back(1);
        }
        return *this;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator ++(int)
{
        uinteger old = *this;
        ++*this;
        return old;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator --()
{
        iterator cur = begin();
        while (cur != end() && *cur == 0) { *cur++ = max_digit; }
        if (cur != end())
        {
                --(*cur);
                normalize();
        }
        else
        {
                // got negative uinteger, do nothing

        }
        return *this;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator --(int)
{
        uinteger old = *this;
        --*this;
        return old;
}


template <typename traits>
void uinteger<traits>::add_digits(digit& d1, digit d2, digit& carry)
{
        double_digit d = static_cast<double_digit>(d1) + d2 + carry;
        d1 = static_cast<digit>(d % end_digit);
        carry = static_cast<digit>(d / end_digit);
}

template <typename traits>
typename uinteger<traits>::digit uinteger<traits>::add(iterator b, iterator e, const uinteger& rhs)
{
        ASSERT(distance(b, e) - rhs.size() >= 0);
        digit carry = 0;
        for (const_iterator it_that = rhs.begin(); it_that != rhs.end(); ++b, ++it_that)
        {
                add_digits(*b, *it_that, carry);
        }
        // now if this is still not ended and there is something in (to) carry...
        for (; carry != 0 && b != e; ++b)
        {
                add_digits(*b, 0, carry);
        }
        return carry;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator += (const uinteger& rhs)
{
        size_type max_size = std::max(size(), rhs.size());
        resize(max_size, 0);
        digit carry = add(begin(), end(), rhs);
        // if there is a carry, append it
        if (carry != 0)
        {
                push_back(carry);
        }
        return *this;
}

template <typename traits>
void uinteger<traits>::sub_digits(digit& d1, digit d2, digit& borrow)
{
        double_digit d = d1 - d2 + borrow + max_digit;
        d1 = d % end_digit;
        borrow = d / end_digit;
}

template <typename traits>
bool uinteger<traits>::subtract(const uinteger& rhs)
{
        size_type max_size = std::max(size(), rhs.size());
        resize(max_size, 0);
        bool result = subtract(begin(), end(), rhs);
        normalize();
        return result;
}

template <typename traits>
bool uinteger<traits>::subtract(iterator b, iterator e, const uinteger& rhs)
{
        ASSERT(distance(b, e) - rhs.size() >= 0);
        digit borrow = 1;
        for (const_iterator it_that = rhs.begin(); it_that != rhs.end(); ++b, ++it_that)
        {
                sub_digits(*b, *it_that, borrow);
        }
        // now if this is still not ended and there is something in (to) borrow...
        for (; borrow != 1 && b != e; ++b)
        {
                sub_digits(*b, 0, borrow);
        }
        // if still there is a borrow, then we were given greater number to subtract than we could
        return borrow == 1;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator -= (const uinteger& rhs)
{
        subtract(rhs);
        return *this;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator *= (const uinteger& rhs)
{
        uinteger w = *this;
        *this = zero;
        return mul(w, rhs);
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator *= (digit d)
{
        if (d == 0)
        {
                *this = zero;
                return *this;
        }
        iterator it_this = begin();
        digit carry = 0;
        double_digit uc = d;
        for (iterator it = begin(); it != end(); ++it)
        {
                double_digit t = uc * *it + carry;
                *it = t % end_digit;
                carry = t / end_digit;
        }
        // if still there is a carry, then append it
        if (carry != 0)
        {
                push_back(carry);
        }
        return *this;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator /= (const uinteger& rhs)
{
        uinteger div;
        divmod(rhs, div);
        return *this = div;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator /= (digit rhs)
{
        uinteger div;
        divmod(rhs, div);
        return *this = div;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator %= (const uinteger& rhs)
{
        uinteger div;
        uinteger mode = divmod(rhs, div);
        return *this = mode;
}

template <typename traits>
uinteger<traits>& uinteger<traits>::operator %= (digit rhs)
{
        uinteger div;
        digit mode = divmod(rhs, div);
        return *this = uinteger(mode);
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator +(const uinteger& rhs) const
{
        return uinteger(*this) += rhs;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator -(const uinteger& rhs) const
{
        return uinteger(*this) -= rhs;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator *(const uinteger& rhs) const
{
        return uinteger(*this) *= rhs;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator *(digit rhs) const
{
        return uinteger(*this) *= rhs;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator /(const uinteger& rhs) const
{
        return uinteger(*this) /= rhs;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator /(digit rhs) const
{
        return uinteger(*this) /= rhs;
}

template <typename traits>
uinteger<traits> uinteger<traits>::operator %(const uinteger& rhs) const
{
        return uinteger(*this) %= rhs;
}

template <typename traits>
typename uinteger<traits>::digit uinteger<traits>::operator %(digit rhs) const
{
        uinteger div;
        return divmod(rhs, div);
}

template <typename traits>
bool uinteger<traits>::operator <(const uinteger& rhs) const
{
        uinteger tmp(*this);
        return !tmp.subtract(rhs);
}

template <typename traits>
bool uinteger<traits>::operator >(const uinteger& rhs) const
{
        return rhs < *this;
}

template <typename traits>
bool uinteger<traits>::operator ==(const uinteger& rhs) const
{
        //   return !(rhs < *this) && !(*this < rhs);
        if (size() != rhs.size())
        {
                return false;
        }
        return equal(begin(), end(), rhs.begin());
}

template <typename traits>
bool uinteger<traits>::operator !=(const uinteger& rhs) const
{
        return !(*this == rhs);
}

template <typename traits>
bool uinteger<traits>::operator <=(const uinteger& rhs) const
{
        return !(rhs < *this);
}

template <typename traits>
bool uinteger<traits>::operator >=(const uinteger& rhs) const
{
        return !(*this < rhs);
}

template <typename traits>
uinteger<traits>& uinteger<traits>::mul(const uinteger& u, const uinteger& v)
{
        resize(u.size() + v.size(), 0);

        iterator it_this = begin();
        const uinteger *pu, *pv;
        if (u.size() < v.size())
        {
                pu = &u; pv = &v;
        }
        else
        {
                pu = &v; pv = &u;
        }
        // pu points to the smaller one
        for (const_iterator it_u = pu->begin(); it_u != pu->end(); ++it_u, ++it_this)
        {
                double_digit uc = *it_u;
                if (uc == 0) continue;
                iterator it_m(it_this);
                digit carry = 0;
                for (const_iterator it_v = pv->begin(); it_v != pv->end(); ++it_v, ++it_m)
                {
                        double_digit t = uc * *it_v + *it_m + carry;
                        *it_m = t % end_digit;
                        carry = t / end_digit;
                }
                *it_m += carry;
        }
        normalize();
        return *this;
}

template <typename traits>
typename uinteger<traits>::digit uinteger<traits>::divmod(digit d, uinteger& result) const
{
        if (d == 0)
        {
                throw division_by_zero();
        }
        uinteger tmp = *this;
        digit mode = divmod(tmp.rbegin(), tmp.rend(), d, result);
        result.normalize();
        return mode;
}

template <typename traits>
uinteger<traits> uinteger<traits>::divmod(uinteger v, uinteger& res) const
{
        if (v.size() == 1)
        {
                // in case it's just a digit
                return uinteger(divmod(v.back(), res));
        }

        if (v == zero)
        {
                throw division_by_zero();
        }

        if (*this < v)
        {
                res = zero;
                return *this;
        }

        digits result;
        result.reserve(size() + 1 - v.size());

        digit d = end_digit / (v.back() + 1); // as v.back() > 0, this will be end_digit/2 at least
        uinteger u = *this;
        if (d != 1)
        {
                u *= d;
                v *= d;
        }
        if (u.size() == size())
        {
                u.push_back(0); // a temporarily denormalized integer
        }

        reverse_iterator it_j = u.rbegin();
        reverse_iterator it_e = it_j; advance(it_e, v.size() + 1);

        for (; it_e != u.rend(); ++it_j, ++it_e)
        {
                result.push_back(divmod(it_j, it_e, v));
        }
        result.push_back(divmod(it_j, it_e, v)); // call it once more with end() (which it_e is now)

        uinteger mode;
        divmod(it_j, it_e, d, mode);

        res = result;
        mode.normalize();
        return mode;
}

template <typename traits>
uinteger<traits> uinteger<traits>::modexp(const uinteger& exp, const uinteger& mod) const
{
        if (exp == zero)
        {
                return mod;
        }
        if (exp == one)
        {
                // recursion base
                return *this % mod;
        }
        uinteger exp_half(exp/2);
        uinteger rec_result = modexp(exp_half, mod);
        uinteger c = (rec_result * rec_result) % mod;
        if (exp.is_odd())
        {
                c = *this * c % mod;
        }
        return c;
}

template<class It, class Diff>
inline It advance_it(It it, Diff d)
{
        advance(it, d);
        return it;
}

template <typename traits>
typename uinteger<traits>::digit uinteger<traits>::divmod(reverse_iterator b, reverse_iterator e, const uinteger& v)
{
        // divide [b...e) by v, update b..e and return quotient digit
        ASSERT(v.size() >= 2);
        ASSERT(distance(b, e) - v.size() == 1);
        digit q;
        if (*b == v.back())
        {
                q = max_digit;
        }
        else
        {
                double_digit uj = *b, uj_1 = *advance_it(b, 1), v1 = v.back();
                q = (end_digit * uj + uj_1) / v1;
        }
        uinteger u_i(digits(b, advance_it(b, 3)));
        uinteger v_i(digits(v.rbegin(), advance_it(v.rbegin(), 2)));
        while (v_i * q > u_i)
        {
                q--;
        }
        uinteger vq = v * q;
        bool more = subtract(e.base(), b.base(), vq);
        if (!more)
        {
                // we got to subtract 1 from q and add that 1's part v to the range
                --q;
                add(e.base(), b.base(), v); // and ignore carry
        }
        return q;
}

template <typename traits>
typename uinteger<traits>::digit uinteger<traits>::div_digits(digit& nom, digit d)
{
        digit result = nom / d;
        nom -= d * result;
        return result;
}

template <typename traits>
typename uinteger<traits>::digit uinteger<traits>::
divmod(const_reverse_iterator b, const_reverse_iterator e, digit d, uinteger& r)
{
        if (b == e)
        {
                ASSERT(false);
                return d;
        }
        digits result;
        result.reserve(distance(b, e));
        digit c = 0;
        for (; b != e; ++b)
        {
                digit this_digit = *b;
                double_digit dd = c * end_digit + this_digit;
                digit d1 = dd / d;
                digit d2 = dd % d;
                result.push_back(d1);
                c = d2;
        }
        r = result;
        return c;
}

template <typename traits>
bool uinteger<traits>::is_digit() const
{
        return size() == 1;
}

template <typename traits>
bool uinteger<traits>::is_odd() const
{
        return front() % 2 == 1;
}

template <typename traits>
void uinteger<traits>::to_string(string& s) const
{
        ASSERT(s.empty());
        s.clear();

        digit base(10);
        uinteger tmp = *this;
        while (tmp != zero)
        {
                uinteger div;
                digit mode = tmp.divmod(base, div);
                s += traits::char_traits::to_char(mode);
                tmp.swap(div);
        }
        if (s.empty())
        {
                s = '0';
        }
        std::reverse(s.begin(), s.end());
}

template <typename traits>
void uinteger<traits>::from_string(const string& s)
{
        ASSERT(!s.empty());
        *this = zero;
        if (s.empty())
        {
                return;
        }
        check_invalid_string(s);
        const digit base(10);
        for (typename string::const_iterator it = s.begin(); it != s.end(); ++it)
        {
                *this *= base;
                *this += uinteger(traits::char_traits::from_char(*it));
        }
}

template <typename traits>
void uinteger<traits>::from_int(unsigned int i)
{
        clear();
        while (i != 0)
        {
                push_back(i % end_digit);
                i /= end_digit;
        }
        if (empty())
        {
                push_back(0);
        }
}

template <typename traits>
uinteger<traits>::operator string () const
{
        string s;
        to_string(s);
        return s;
}

static int random_char(int)
{
        return '0' + rand() % 10;
}

template <typename traits>
uinteger<traits> uinteger<traits>::decimal_rand(size_type size)
{
        string x(size, 0);
        transform(x.begin(), x.end(), x.begin(), random_char);
        uinteger u(x);
        if (size > 1)
        {
                // normalization
                if (u.back() == 0)
                {
                        ++u.back();
                }
        }
        return u;
}

template <typename traits>
void uinteger<traits>::swap(uinteger& rhs)
{
        base_type::swap(rhs);
}

template <typename traits>
typename uinteger<traits>::const_iterator uinteger<traits>::data_begin() const
{
        return begin();
}

template <typename traits>
typename uinteger<traits>::const_iterator uinteger<traits>::data_end() const
{
        return end();
}

template <typename traits>
const uinteger<traits> uinteger<traits>::zero = uinteger((digit)0);
template <typename traits>
const uinteger<traits> uinteger<traits>::one = uinteger((digit)1);

BIG_NUMBERS_NAMESPACE_END

#endif // __BIG_INTEGER_TCC__
